# Divisibility in Z

Definition: Let $a, b \in \mathbb{Z}$, we say that $a$ divides $b$, when $\exists \,\,q \in \mathbb{Z} : b = aq$. Denoted with $a|b$. We can also say that $b$ is a multiple of $a$, or that $a$ is a divisor of $b$.

The basic properties of the relation of divisibility in the ring of whole numbers are collected in the first theorem.

Theorem 1: For any numbers $a, b, c, d \in \mathbb{Z}$. (Proof & exercises at the end of the note).

1. $a|a$, $1|a$, $(-1)|a$, $a|0$.
2. $a|b \land b|c \implies a|c$
3. $a|b \land b|a \implies a = \pm b$
4. $a|b \land a|c \implies a|b \pm c \land a|bd$
5. $a^k|b^k$ for $k \geqslant 1$ $\implies a|b$.

Theorem 2: $a|b \land b \neq 0 \implies |a| \leqslant |b|$.

Theorem 3: Let $a_i, x_i, b_j, y_j, c \in \mathbb{Z}$. Then if

holds, and $\exists d : \forall a_i, b_j : d | a_i \land d | b_i$, then $d|c$.

Example: We will proof that the number $A_n = 5^{2n} + 1$ is, for every natural number n, divisible by 2, but not by 4.

from which $2|A_n$. If $4|A_n$ then, according to T3, we would have $4|2$. QED.

Let's denote the set of all divisors of a whole number $a$ with $\mathcal{D}(a)$. It is trivial that $D(0) = \mathbb{Z}$. If $a, b \in \mathbb{Z}$ then we denote:

Note that the set $\mathcal{D}(a, b)$ is always not empty ( $a \in \mathcal{D}(a,b)$, T1.1 ); Set $\mathcal{D}(0, 0) = \mathbb{Z}$ In all other cases the set $\mathcal{D}(a, b)$ is finite ( $a \neq 0 \implies \mathcal{D}(a, b) \subset [\ -|a|; |a|\ ]$, T2 ).

If $a^2 + b^2 > 0$ then the biggest element of $\mathcal{D}(a, b)$ is the biggest common divisor of $a$ and $b$.

Theorem 3: (Division with remainder in $\mathbb{Z}$) If $a, b \in \mathbb{Z}$ and $b \neq 0$ then, there exists exactly one pair of numbers $q, r \in \mathbb{Z}$, such that:

The number $r$ is a remainder of dividing $a$ by $b$. The possible remainders of dividing whole numbers by natural number $n$ are numbers:

These numbers are called the Complete residue system modulo m.